package DynamicProgramming;//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
//
// 返回符合要求的 最少分割次数 。 
//
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：1
//解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
// 
//
// 示例 2： 
//
// 
//输入：s = "a"
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：s = "ab"
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 2000 
// s 仅由小写英文字母组成 
// 
// 
// 
// Related Topics 字符串 动态规划 👍 487 👎 0


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class minCutII {

    public int minCut(String s) {
        //特例
        if(s==null || s.length()==0 || s.length()==1){
            return 0;
        }
        int len = s.length();
        //dp[i][j]  表示i到j的子串是不是回文串
        boolean[][] dp = new boolean[len][len];
        //初始化
        for(int i=0;i<len;i++){
            dp[i][i] = true;
        }
        for (int j = 1;j < len;j++){
            for (int i = 0; i < j; i++) {
                // 头尾字符不相等，不是回文串
                if (s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    // 相等的情况下
                    // 考虑头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串
                    // (j-1)-(i+1)+1 < 2   =  j - i < 3
                    if (j - i < 3){
                        dp[i][j] = true;
                    }else {
                        // 状态转移
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
            }
        }

        //steps[i] 表示以0-i分割为回文的最小次数
        int[] steps = new int[len];
        Arrays.fill(steps,len-1);  //初始化为最大长度减1次
        for(int i=0;i<len;i++){
            if(dp[0][i]){
                //o-i是回文串
                steps[i] = 0;  //不需要分割
            }else{
                //0-i不是回文，那么我们枚举最后一个回文串的起始位置 j+1，
                //保证 s[j+1,i] 是一个回文串，那么f[i]就可以从f[j]转移而来，附加1次额外的分割次数。
                //但有可能本身[0,i]是回文，所以要取最小的。
                for(int j=0;j<i;j++){
                    //遍历
                    if (dp[j + 1][i]) {
                        steps[i] = Math.min(steps[i], steps[j] + 1);
                    }

                }
            }

        }

        return steps[len-1];

    }
}
//leetcode submit region end(Prohibit modification and deletion)
